package algorithm.leetcode.medium;

/*
 给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），
 可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
 */

import java.util.Arrays;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/28
 */
public class Question287 {

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 2, 4};
        Question287 question = new Question287();
        int duplicate = question.findDuplicate1(nums);
        System.out.println(duplicate);
    }

    public int findDuplicate(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int len = nums.length;
        int left = 1;
        int right = len - 1;
        while (left < right) {
            int mid = (left + right + 1) >>> 1;
            int n = 0;
            for (int num : nums) {
                if (num < mid) {
                    n += 1;
                }
            }
            if (n >= mid) {
                // 说明在左边[left, mid - 1]
                right = mid - 1;
            } else {
                // 右边[mid, right]
                left = mid;
            }
        }
        return left;
    }


    public int findDuplicate1(int[] nums) {
        Arrays.sort(nums);
        int pre = nums[0];
        int num;
        for (int i = 1; i < nums.length; i++) {
            num = nums[i];
            if (num == pre) {
                return num;
            }
            pre = num;
        }
        return -1;
    }
}
